/* 最长公共子序列 */

#include<iostream>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;

constexpr int MAXLEN = 201;

void CalcLCS(const char* str1, const char* str2)
{
	int maxLen[MAXLEN][MAXLEN];
	int lcsIdx[MAXLEN]{ -1, 0 };

	int len1 = strlen(str1);
	int len2 = strlen(str2);

	for (int i = 0; i < len1; i++)
	{
		for (int j = 0; j < len2; j++)
		{
			if (str1[i] == str2[j])
			{
				int newLen = 0;
				if (i == 0 || j == 0)
				{
					newLen = 1;
				}
				else
				{
					newLen = maxLen[i - 1][j - 1] + 1;
				}
				maxLen[i][j] = newLen;
				lcsIdx[newLen - 1] = i;
			}
			else
			{
				int len1, len2;
				len1 = (i == 0 ? 0 : maxLen[i - 1][j]);
				len2 = (j == 0 ? 0 : maxLen[i][j - 1]);
				maxLen[i][j] = max(len1, len2);
			}
		}
	}

	int finalLen = maxLen[len1 - 1][len2 - 1];
	cout << "LCS Len = " << finalLen << "\t";
	for_each(lcsIdx, lcsIdx + finalLen, [&str1](int e) -> void {cout << str1[e]; });
	cout << "\n";
}


int main(void)
{

	CalcLCS("abcfbc", "abfcab");
	CalcLCS("programming", "contest");
	CalcLCS("abcd", "mnp");
}

